home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 1997 #1 / Amiga Plus CD - 1997 - No. 01.iso / pd / programmierung / mesa-1.2.8 / src-glu / tesselat.c < prev   
C/C++ Source or Header  |  1996-05-27  |  10KB  |  435 lines
  1. /* tesselat.c */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  1.2
  6.  * Copyright (C) 1995  Brian Paul  (brianp@ssec.wisc.edu)
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25. $Id: tesselat.c,v 1.6 1995/09/19 13:43:51 brianp Exp $
  26.  
  27. $Log: tesselat.c,v $
  28.  * Revision 1.6  1995/09/19  13:43:51  brianp
  29.  * removed #include "gluP.h" per Bogdan Sikorski
  30.  *
  31.  * Revision 1.5  1995/08/04  13:09:59  brianp
  32.  * include gluP.h to define NULL, just in case
  33.  *
  34.  * Revision 1.4  1995/06/09  16:42:31  brianp
  35.  * renamed as tesselat.c
  36.  *
  37.  * Revision 1.3  1995/05/23  17:37:48  brianp
  38.  * added #ifndef NULL ...
  39.  *
  40.  * Revision 1.2  1995/05/22  16:56:20  brianp
  41.  * Release 1.2
  42.  *
  43.  * Revision 1.1  1995/04/28  16:21:08  brianp
  44.  * Initial revision
  45.  *
  46.  */
  47.  
  48.  
  49. /*
  50.  * This file is part of the polygon tesselation code contributed by
  51.  * Bogdan Sikorski
  52.  */
  53.  
  54.  
  55. #include <stdlib.h>
  56. #include <math.h>
  57. #include "tess.h"
  58.  
  59.  
  60.  
  61. static GLboolean edge_flag;
  62.  
  63. static void emit_triangle(GLUtriangulatorObj *, tess_vertex *,
  64.     tess_vertex *,tess_vertex *);
  65.  
  66. static void emit_triangle_with_edge_flag(GLUtriangulatorObj *,
  67.      tess_vertex *,GLboolean,tess_vertex *,GLboolean,
  68.      tess_vertex *,GLboolean);
  69.  
  70. static GLdouble twice_the_triangle_area(
  71.     tess_vertex *va,
  72.     tess_vertex *vb,
  73.     tess_vertex *vc)
  74. {
  75.     return     (vb->x - va->x)*(vc->y - va->y) - (vb->y - va->y)*(vc->x - va->x);
  76. }
  77.  
  78. static GLboolean left(
  79.     GLdouble A,
  80.     GLdouble B,
  81.     GLdouble C,
  82.     GLdouble x,
  83.     GLdouble y)
  84. {
  85.     if(A*x+B*y+C > -EPSILON)
  86.         return GL_TRUE;
  87.     else
  88.         return GL_FALSE;
  89. }
  90.  
  91. static GLboolean right(
  92.     GLdouble A,
  93.     GLdouble B,
  94.     GLdouble C,
  95.     GLdouble x,
  96.     GLdouble y)
  97. {
  98.     if(A*x+B*y+C < EPSILON)
  99.         return GL_TRUE;
  100.     else
  101.         return GL_FALSE;
  102. }
  103.  
  104. static GLboolean convex_ccw(
  105.     tess_vertex *va,
  106.     tess_vertex *vb,
  107.     tess_vertex *vc,
  108.     GLUtriangulatorObj *tobj)
  109. {
  110.     if(twice_the_triangle_area(va,vb,vc) > EPSILON)
  111.         return GL_TRUE;
  112.     else
  113.         return GL_FALSE;
  114. }
  115.  
  116. static GLboolean convex_cw(
  117.     tess_vertex *va,
  118.     tess_vertex *vb,
  119.     tess_vertex *vc,
  120.     GLUtriangulatorObj *tobj)
  121. {
  122.     if(twice_the_triangle_area(va,vb,vc) < -EPSILON)
  123.         return GL_TRUE;
  124.     else
  125.         return GL_FALSE;
  126. }
  127.  
  128. static GLboolean diagonal_ccw(
  129.     tess_vertex *va,
  130.     tess_vertex *vb,
  131.     GLUtriangulatorObj *tobj,
  132.     tess_contour *contour)
  133. {
  134.     tess_vertex *vc=va->next , *vertex , *shadow_vertex;
  135.     struct
  136.     {
  137.         GLdouble A,B,C;
  138.     } ac,cb,ba;
  139.     GLdouble x,y;
  140.  
  141.     if(convex_ccw(va,vc,vb,tobj)==GL_FALSE)
  142.         return GL_FALSE;
  143.     ba.A=vb->y - va->y;
  144.     ba.B=va->x - vb->x;
  145.     ba.C= -ba.A*va->x - ba.B*va->y;
  146.     ac.A=va->y - vc->y;
  147.     ac.B=vc->x - va->x;
  148.     ac.C= -ac.A*vc->x - ac.B*vc->y;
  149.     cb.A=vc->y - vb->y;
  150.     cb.B=vb->x - vc->x;
  151.     cb.C= -cb.A*vb->x - cb.B*vb->y;
  152.     for(vertex=vb->next;vertex!=va;vertex=vertex->next)
  153.     {
  154.         shadow_vertex=vertex->shadow_vertex;
  155.         if(shadow_vertex!=NULL && 
  156.             (shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
  157.             continue;
  158.         x=vertex->x;
  159.         y=vertex->y;
  160.         if(left(ba.A,ba.B,ba.C,x,y) &&
  161.             left(ac.A,ac.B,ac.C,x,y) &&
  162.             left(cb.A,cb.B,cb.C,x,y))
  163.             return GL_FALSE;
  164.     }
  165.     return GL_TRUE;
  166. }
  167.  
  168. static GLboolean diagonal_cw(
  169.     tess_vertex *va,
  170.     tess_vertex *vb,
  171.     GLUtriangulatorObj *tobj,
  172.     tess_contour *contour)
  173. {
  174.     tess_vertex *vc=va->next , *vertex , *shadow_vertex;
  175.     struct
  176.     {
  177.         GLdouble A,B,C;
  178.     } ac,cb,ba;
  179.     GLdouble x,y;
  180.  
  181.     if(convex_cw(va,vc,vb,tobj)==GL_FALSE)
  182.         return GL_FALSE;
  183.     ba.A=vb->y - va->y;
  184.     ba.B=va->x - vb->x;
  185.     ba.C= -ba.A*va->x - ba.B*va->y;
  186.     ac.A=va->y - vc->y;
  187.     ac.B=vc->x - va->x;
  188.     ac.C= -ac.A*vc->x - ac.B*vc->y;
  189.     cb.A=vc->y - vb->y;
  190.     cb.B=vb->x - vc->x;
  191.     cb.C= -cb.A*vb->x - cb.B*vb->y;
  192.     for(vertex=vb->next;vertex!=va;vertex=vertex->next)
  193.     {
  194.         shadow_vertex=vertex->shadow_vertex;
  195.         if(shadow_vertex!=NULL && 
  196.             (shadow_vertex==va || shadow_vertex==vb || shadow_vertex==vc))
  197.             continue;
  198.         x=vertex->x;
  199.         y=vertex->y;
  200.         if(right(ba.A,ba.B,ba.C,x,y) &&
  201.             right(ac.A,ac.B,ac.C,x,y) &&
  202.             right(cb.A,cb.B,cb.C,x,y))
  203.             return GL_FALSE;
  204.     }
  205.     return GL_TRUE;
  206. }
  207.  
  208. static void clip_ear(
  209.     GLUtriangulatorObj *tobj,
  210.     tess_vertex *v,
  211.     tess_contour *contour)
  212. {
  213.     emit_triangle(tobj,v->previous,v,v->next);
  214.     /* the first in the list */
  215.     if(contour->vertices==v)
  216.     {
  217.         contour->vertices=v->next;
  218.         contour->last_vertex->next=v->next;
  219.         v->next->previous=contour->last_vertex;
  220.     }
  221.     else
  222.     /* the last ? */
  223.     if(contour->last_vertex==v)
  224.     {
  225.         contour->vertices->previous=v->previous;
  226.         v->previous->next=v->next;
  227.         contour->last_vertex=v->previous;
  228.     }
  229.     else
  230.     {
  231.         v->next->previous=v->previous;
  232.         v->previous->next=v->next;
  233.     }
  234.     free(v);
  235.     --(contour->vertex_cnt);
  236. }
  237.  
  238. static void clip_ear_with_edge_flag(
  239.     GLUtriangulatorObj *tobj,
  240.     tess_vertex *v,
  241.     tess_contour *contour)
  242. {
  243.     emit_triangle_with_edge_flag(tobj,v->previous,v->previous->edge_flag,
  244.         v,v->edge_flag,v->next,GL_FALSE);
  245.     v->previous->edge_flag=GL_FALSE;
  246.     /* the first in the list */
  247.     if(contour->vertices==v)
  248.     {
  249.         contour->vertices=v->next;
  250.         contour->last_vertex->next=v->next;
  251.         v->next->previous=contour->last_vertex;
  252.     }
  253.     else
  254.     /* the last ? */
  255.     if(contour->last_vertex==v)
  256.     {
  257.         contour->vertices->previous=v->previous;
  258.         v->previous->next=v->next;
  259.         contour->last_vertex=v->previous;
  260.     }
  261.     else
  262.     {
  263.         v->next->previous=v->previous;
  264.         v->previous->next=v->next;
  265.     }
  266.     free(v);
  267.     --(contour->vertex_cnt);
  268. }
  269.  
  270. static void triangulate_ccw(
  271.     GLUtriangulatorObj *tobj,
  272.     tess_contour *contour)
  273. {
  274.     tess_vertex *vertex;
  275.     GLuint vertex_cnt=contour->vertex_cnt;
  276.  
  277.     while(vertex_cnt > 3)
  278.     {
  279.         vertex=contour->vertices;
  280.         while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  281.             tobj->error==GLU_NO_ERROR)
  282.             vertex=vertex->next;
  283.         if(tobj->error!=GLU_NO_ERROR)
  284.             return;
  285.         clip_ear(tobj,vertex->next,contour);
  286.         --vertex_cnt;
  287.     }
  288. }
  289.  
  290. static void triangulate_cw(
  291.     GLUtriangulatorObj *tobj,
  292.     tess_contour *contour)
  293. {
  294.     tess_vertex *vertex;
  295.     GLuint vertex_cnt=contour->vertex_cnt;
  296.  
  297.     while(vertex_cnt > 3)
  298.     {
  299.         vertex=contour->vertices;
  300.         while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  301.             tobj->error==GLU_NO_ERROR)
  302.             vertex=vertex->next;
  303.         if(tobj->error!=GLU_NO_ERROR)
  304.             return;
  305.         clip_ear(tobj,vertex->next,contour);
  306.         --vertex_cnt;
  307.     }
  308. }
  309.  
  310. static void triangulate_ccw_with_edge_flag(
  311.     GLUtriangulatorObj *tobj,
  312.     tess_contour *contour)
  313. {
  314.     tess_vertex *vertex;
  315.     GLuint vertex_cnt=contour->vertex_cnt;
  316.  
  317.     while(vertex_cnt > 3)
  318.     {
  319.         vertex=contour->vertices;
  320.         while(diagonal_ccw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  321.             tobj->error==GLU_NO_ERROR)
  322.             vertex=vertex->next;
  323.         if(tobj->error!=GLU_NO_ERROR)
  324.             return;
  325.         clip_ear_with_edge_flag(tobj,vertex->next,contour);
  326.         --vertex_cnt;
  327.     }
  328. }
  329.  
  330. static void triangulate_cw_with_edge_flag(
  331.     GLUtriangulatorObj *tobj,
  332.     tess_contour *contour)
  333. {
  334.     tess_vertex *vertex;
  335.     GLuint vertex_cnt=contour->vertex_cnt;
  336.  
  337.     while(vertex_cnt > 3)
  338.     {
  339.         vertex=contour->vertices;
  340.         while(diagonal_cw(vertex,vertex->next->next,tobj,contour)==GL_FALSE &&
  341.             tobj->error==GLU_NO_ERROR)
  342.             vertex=vertex->next;
  343.         if(tobj->error!=GLU_NO_ERROR)
  344.             return;
  345.         clip_ear_with_edge_flag(tobj,vertex->next,contour);
  346.         --vertex_cnt;
  347.     }
  348. }
  349.  
  350. void tess_tesselate(GLUtriangulatorObj *tobj)
  351. {
  352.     tess_contour *contour;
  353.  
  354.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  355.     {
  356.         if(contour->orientation==GLU_CCW)
  357.             triangulate_ccw(tobj,contour);
  358.         else
  359.             triangulate_cw(tobj,contour);
  360.         if(tobj->error!=GLU_NO_ERROR)
  361.             return;
  362.         /* emit the last triangle */
  363.         emit_triangle(tobj,contour->vertices,contour->vertices->next,
  364.             contour->vertices->next->next);
  365.     }
  366. }
  367.  
  368. void tess_tesselate_with_edge_flag(GLUtriangulatorObj *tobj)
  369. {
  370.     tess_contour *contour;
  371.  
  372.     edge_flag=GL_TRUE;
  373.     /* first callback with edgeFlag set to GL_TRUE */
  374.     (tobj->callbacks.edgeFlag)(GL_TRUE);
  375.  
  376.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  377.     {
  378.         if(contour->orientation==GLU_CCW)
  379.             triangulate_ccw_with_edge_flag(tobj,contour);
  380.         else
  381.             triangulate_cw_with_edge_flag(tobj,contour);
  382.         if(tobj->error!=GLU_NO_ERROR)
  383.             return;
  384.         /* emit the last triangle */
  385.         emit_triangle_with_edge_flag(tobj,contour->vertices,
  386.             contour->vertices->edge_flag,contour->vertices->next,
  387.             contour->vertices->next->edge_flag,contour->vertices->next->next,
  388.             contour->vertices->next->next->edge_flag);
  389.     }
  390. }
  391.  
  392. static void emit_triangle(
  393.     GLUtriangulatorObj *tobj,
  394.     tess_vertex *v1,
  395.     tess_vertex *v2,
  396.     tess_vertex *v3)
  397. {
  398.     (tobj->callbacks.begin)(GL_TRIANGLES);
  399.     (tobj->callbacks.vertex)(v1->data);
  400.     (tobj->callbacks.vertex)(v2->data);
  401.     (tobj->callbacks.vertex)(v3->data);
  402.     (tobj->callbacks.end)();
  403. }
  404.  
  405. static void emit_triangle_with_edge_flag(
  406.     GLUtriangulatorObj *tobj,
  407.     tess_vertex *v1,
  408.     GLboolean edge_flag1,
  409.     tess_vertex *v2,
  410.     GLboolean edge_flag2,
  411.     tess_vertex *v3,
  412.     GLboolean edge_flag3)
  413. {
  414.     (tobj->callbacks.begin)(GL_TRIANGLES);
  415.     if(edge_flag1!=edge_flag)
  416.     {
  417.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  418.         (tobj->callbacks.edgeFlag)(edge_flag);
  419.     }
  420.     (tobj->callbacks.vertex)(v1->data);
  421.     if(edge_flag2!=edge_flag)
  422.     {
  423.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  424.         (tobj->callbacks.edgeFlag)(edge_flag);
  425.     }
  426.     (tobj->callbacks.vertex)(v2->data);
  427.     if(edge_flag3!=edge_flag)
  428.     {
  429.         edge_flag = (edge_flag==GL_TRUE ? GL_FALSE : GL_TRUE);
  430.         (tobj->callbacks.edgeFlag)(edge_flag);
  431.     }
  432.     (tobj->callbacks.vertex)(v3->data);
  433.     (tobj->callbacks.end)();
  434. }
  435.